'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-18 09:47:18
'''
#
# @lc app=leetcode.cn id=134 lang=python3
#
# [134] 加油站
#

# @lc code=start
# 遍历一遍。证明比较复杂，设不可跨越点集合为{y_i},i>0且设y_0=-1，则可知数据满足
# \sum_{k=y_i+1}^{y_{i+1}-1}(g_k-c_k)>0, g_{y_i}<c_{y_i}且\sum_{k=y_i+1}^{y_{i+1}}(g_k-c_k)<0
# 如果整体\sum_{k=0}^{N}(g_k-c_k)>=0的，总会找到一个点可以循环完。比如y_f+1。因为
# 反正法。如果从y_f+1出发，不能跨越y_j点的话，则从y_f+1到y_j，整体为负的。因为从y_j+1到y_f整体也为负的。
# 这个时候从0到N的求和肯定为fu的。与整体为非负矛盾。
from typing import List
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        ans, tot, cur, n = 0, 0, 0, len(gas)
        for i in range(n):
            tot+=gas[i]-cost[i]
            cur+=gas[i]-cost[i]
            if cur<0:
                cur, ans = 0, i+1
        return ans if tot>=0 else -1
        

# @lc code=end

